#ifndef SAFE_ALGORITHM_H
#define SAFE_ALGORITHM_H

namespace safe_stl
{


template<class Iterator>
void merge_sort_internal(Iterator start,Iterator end,Iterator tempStart, Iterator tempEnd)
{
   if(end - start == 1)
     return;
   int delta = end - start;
   int deltad2 = delta / 2;
   merge_sort_internal(start,start + deltad2,tempStart,tempStart + deltad2);
   merge_sort_internal(start + deltad2,end,tempStart + deltad2,tempEnd);
   Iterator p1 =  start;
   Iterator p2 =  start + deltad2;
   Iterator pTemp = tempStart;
   while( p1 != (start + deltad2) && p2 != end)
   {
      while( p1 != (start + deltad2) && *p1 <= *p2)
        *pTemp++ = *p1++;
      while( p2 != end && *p2 <= *p1)
        *pTemp++ = *p2++;
   }
   while( p1 != (start + deltad2) )
        *pTemp++ = *p1++;
   while( p2 != end )
        *pTemp++ = *p2++;
   //copy back to origin
   for(;start != end;start++,tempStart++)
   {
      *start = *tempStart;
   }
}

template<class Iterator>
void merge_sort(Iterator start,Iterator end)
{
   safe_stl::vector<typename Iterator::ElemType> temp;
   temp.resize(end - start  );

   merge_sort_internal(start,end,temp.begin(),temp.end()); 
}

template<class Iterator>
void sort(Iterator start,Iterator end)
{
    merge_sort(start,end);
}

}
#endif
